import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：3
 * 输出：
 * [
 *   [1,null,3,2],
 *   [3,2,null,1],
 *   [3,1,null,null,2],
 *   [2,1,3],
 *   [1,null,2,null,3]
 * ]
 * 解释：
 * 以上的输出对应以下 5 种不同结构的二叉搜索树：
 * <p>
 * 1         3     3      2      1
 * \       /     /      / \      \
 * 3     2     1      1   3      2
 * /     /       \                 \
 * 2     1         2                 3
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= n <= 8
 */
class Solution {

    public static void main(String[] args) {
        List<TreeNode> all = generateTrees(3);
        System.out.println(all.size());
    }

    public static List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        if (n == 1) {
            result.add(new TreeNode(1));
            return result;
        }
        for (int i = 1; i <= n; i++) {
            List<TreeNode> leftList = subTree(1, i - 1);
            List<TreeNode> rightList = subTree(i + 1, n);
            if (leftList.isEmpty()) {
                for (TreeNode node : rightList) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.right = node;
                    result.add(treeNode);
                }
            } else if (rightList.isEmpty()) {
                for (TreeNode node : leftList) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = node;
                    result.add(treeNode);
                }
            } else {
                for (TreeNode node : leftList) {
                    for (TreeNode value : rightList) {
                        TreeNode treeNode = new TreeNode(i);
                        treeNode.left = node;
                        treeNode.right = value;
                        result.add(treeNode);
                    }
                }
            }
        }
        return result;
    }

    public static List<TreeNode> subTree(int a, int b) {
        List<TreeNode> result = new ArrayList<>();
        if (a == b) {
            result.add(new TreeNode(a));
            return result;
        }
        for (int i = a; i <= b; i++) {
            List<TreeNode> leftList = subTree(a, i - 1);
            List<TreeNode> rightList = subTree(i + 1, b);
            if (leftList.isEmpty()) {
                for (TreeNode node : rightList) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.right = node;
                    result.add(treeNode);
                }
            } else if (rightList.isEmpty()) {
                for (TreeNode node : leftList) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = node;
                    result.add(treeNode);
                }
            } else {
                for (TreeNode node : leftList) {
                    for (TreeNode value : rightList) {
                        TreeNode treeNode = new TreeNode(i);
                        treeNode.left = node;
                        treeNode.right = value;
                        result.add(treeNode);
                    }
                }
            }
        }
        return result;
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}